
"""
NC45 实现二叉树先序，中序和后序遍历
https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362?tpId=117&&tqId=37819&&companyId=239&rp=1&ru=/company/home/code/239&qru=/ta/job-code-high/question-ranking
"""

from typing import Optional, List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类 the root of binary tree
# @return int整型二维数组
#


class Solution:

    def inorder_recursion(self, root: Optional[TreeNode], res: List) -> List[int]:
        """
        中序遍历，递归
        :param root:
        :return:
        """
        if root:
            self.inorder_recursion(root.left, res)
            res.append(root.val)
            self.inorder_recursion(root.right, res)

        return res

    def preorder_recursion(self, root: Optional[TreeNode], res: List) -> List[int]:
        """
        先序遍历，递归
        :param root:
        :param res:
        :return:
        """
        if root:
            res.append(root.val)
            self.preorder_recursion(root.left, res)
            self.preorder_recursion(root.right, res)

        return res

    def postorder_recursion(self, root: Optional[TreeNode], res: List) -> List[int]:
        """
        后序遍历，递归
        :param root: 
        :param res: 
        :return: 
        """
        if root:
            self.postorder_recursion(root.left, res)
            self.postorder_recursion(root.right, res)
            res.append(root.val)

        return res

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """
        中序遍历
        :param root:
        :return:
        """
        # 递归法
        res = []
        res = self.inorder_recursion(root, res)
        return res

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """
        先序遍历
        :param root: 
        :return: 
        """
        # 递归法
        res = []
        res = self.preorder_recursion(root, res)
        return res

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        """
        后序遍历
        :param root: 
        :return: 
        """
        # 递归法
        res = []
        res = self.postorder_recursion(root, res)
        return res

    def threeOrders(self, root: TreeNode) -> List[List[int]]:
        # write code here
        res = []
        res.append(self.preorderTraversal(root))
        res.append(self.inorderTraversal(root))
        res.append(self.postorderTraversal(root))
        return res
